#include <stdio.h>
#include <string.h>
#include "../global.h"
#include "hashtableCloseHash.h"


/*
* 思路
*	闭散列，也就是在最开始定义的数组空间进行插入和查找，发生冲突就下一个，也就是数组元素有3种状态
*	1.空可用2.非空有值不可用3.非空无效，被删除了
*	哈希函数：取余，对key取余，那value呢？
*	发送冲突后，index+1，判断，如果再次发送冲突（也就是直到不发生冲突）index+1，也就是直到Elem状态为Empety，就结束
*	
*	哈希函数
*	哈希表的初始化
*	往哈希表插入元素
*	删除哈希表的某个元素
*	remove哈希表的某个元素，使其不可用，好像和上面一样
*	根据key值和value查找该元素的下标index
*	判断哈希表是否空
*	判断哈希表是否满
*	释放哈希表所占用的空间
*	打印哈希表的所有元素
*/

/*
* 初始化哈希表,根据哈希表大小为其分配空间
*/
/**
 * 或许有更好的哈希函数，
 * */
int HashFunction(KeyType key)
{
	return ( key%HTSIZE );
}

/**
 * 同样传入哈希表所需要申请的空间地址指针
 * */
void InitHt(HASHTABLE* ht,HTELEM* htPointer)
{
	ht->htPointer = htPointer;
	ht->len = 0;
	ht->HashFunc = HashFunction; //对函数名取地址或者不去地址值和意义都一样
	//初始化哈希表的每一个元素
	memset(ht,0,sizeof(*ht)); //全都初始化为可用sizeof(ht) = sizeof(*htPointer) + 4 +4. sizeof(*htPointer) = 4+4+4
}

/**
 * 将键值对插入哈希表
 * INTERROR-fail 1-success 0-already exist //返回值也可以设置为枚举类型
 * */
static int InsertElemToHt(HASHTABLE* ht,KeyType key,ValueType value)
{
	
	//同样进行地址是否有效的判断
	if( ht->htPointer == NULL ) return INTERROR;
	if( ht->len >=HTSIZE ) //同样进行是否越界判断
	{
		printf("Ht is overflow!!!\n");
		return INTERROR;
	}
	//获取下标值
	int index = ht->HashFunc(key);

	while(1)
	{
		if(ht->htPointer[index].key == key) return 0; //存在了
		if(ht->htPointer[index].htState != Valid) //
		{
			ht->htPointer[index].key = key;
			ht->htPointer[index].value = value;
			ht->len++;
			ht->htPointer[index].htState = Valid;
			return 1;
		}
		index++; //首尾不相连，也就是不循环了，那空间得够大
	}

}

/**
 * 根据该元素所在的下标，赋值给key值对应的value，1-success 0-fail，所以
 * 如果同一个key对应多个value呢？所以查找key-value的下标，键值对都需要
 * 看来我还是理解错了key，key值肯定是不一样的，但是取余后可能会一样，所以
 * 此时就需要解决冲突
 * */
int FindElemInHt(HASHTABLE* ht,KeyType key,ValueType* value)
{
	//同样进行地址是否有效的判断
	if( ht->htPointer == NULL ) return INTERROR;
	int index = ht->HashFunc(key);
	if( ht->htPointer[index].key == key && ht->htPointer[index].htState == Valid ) //2个条件同时成立，且前者的优先级大于后者也就是状态
	{
		*value = ht->htPointer[index].value;
		return 1;
	}
	else
	{
		while(ht->htPointer[index].htState != Empety) //不为空就一直找，为空说明哈希表中没有这个元素
		{
			if(ht->htPointer[index].key != key)
			{
				index++;
				if(index >= HTSIZE) //循环查找,查找循环查找，插入不循环？
					index=0;
			}
			else
			{
				if(ht->htPointer[index].htState == Valid)
				{
					*value = ht->htPointer[index].value;
					return 1;
				}
				else
					index++; //或者可以和上面的判断合并
			}
		}
		return 0; //直到为空都没有找到
	}



}

/**
 * 查找key值对应的下标index
 * 1-sucess 0-fail
 * */
int IndexElemInHt(HASHTABLE* ht,KeyType key,int* index)
{
	if( ht->htPointer == NULL ) return INTERROR; //好像可以不用判断因为调用该函数的前面就有判断
	int i = ht->HashFunc(key);
	while( ht->htPointer[i].htState == Valid && (i != (ht->HashFunc(key)%HTSIZE - 1 )))
	{
		if( ht->htPointer[i].key == key )
		{
			*index = i;
			return 1;
		}
		else
		{
			i = i%HTSIZE + 1 ;
		}
	}
	if( ht->htPointer[i].htState == Valid && ht->htPointer[i].key == key )
	{
			*index = i;
			return 1;
	}
	else
	{
		return 0;
	}



}


/**
 * 根据key删除哈希表上的元素，如果该key对应多个value呢？
 * 1-成功 0-失败 
 * */
int DelElemFromHt(HASHTABLE* ht,KeyType key)
{
	//同样进行地址是否有效的判断
	if( ht->htPointer == NULL ) return INTERROR;
	int index = 0;
	if(!IndexElemInHt(ht,key,&index)) return 0;
	ht->htPointer[index].htState = Invalid;
	ht->len--;
	return 1;


}

/**
 * 判断哈希表是否为空
 * 1-空 0-非空
 * */
int IsHtEmpety(HASHTABLE* ht)
{
	if(ht->htPointer) return INTERROR;
	return ( ht->len==0?1:0 );
}


/**
 * 打印哈希表
 * */
static void PrintHt(HASHTABLE* ht)
{
	if(ht->htPointer ==0 || ht->len ==0) return ;
	int i = 0;
	for(i=0;i<HTSIZE;i++)
	{
		if(ht->htPointer[i].htState == Valid)
		{
			printf("number i is %d key is %d value is %d htState is %d\n",i,ht->htPointer[i].key,ht->htPointer[i].value,ht->htPointer[i].htState);
		}
	}
}


/**
 * 释放哈希表所占用的空间
 * */
void Freeht(HASHTABLE* ht)
{
	FREE(ht->htPointer);
}


#ifdef HASHTABLECLOSEHASH_DEBUG
int main(int argc, char const *argv[])
{
	HTELEM* htPointer = (HTELEM*)malloc(sizeof(HTELEM)*HTSIZE);
	HASHTABLE* ht;
	InitHt(ht,htPointer);
	int i = 0;
	for(i=0;i<20;i++)
	{
		InsertElemToHt(ht,i*2,i);
	}

	//PrintHt(ht);



	return 0;
}
#endif

